import java.util.ArrayList;

/**
 * Created by forcht on 2018/5/16.
 */
public class Solution {
    private ArrayList<ArrayList<String>> lists;
    private ArrayList<String> currentList;
    public ArrayList<ArrayList<String>> partition(String s) {
        lists=new ArrayList<>();
        currentList=new ArrayList<>();
        dfs(s,0);
        return lists;
    }
    public void dfs(String s,int left){
        if (currentList.size()>0&&left>=s.length()){
            lists.add((ArrayList<String>) currentList.clone());
        }
        for(int i=left;i<s.length();i++){
            if(isPalindrome(s,left,i)){
                if (left==i)currentList.add(s.charAt(left)+"");
                else currentList.add(s.substring(left,i+1));
                dfs(s,i+1);
                currentList.remove(currentList.size()-1);
            }
        }
    }

    public boolean isPalindrome(String s,int left,int right){
        if (left==right)return true;
        while (left<right){
            if(s.charAt(left)!=s.charAt(right))return false;
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        System.out.println(solution.partition("aab"));
    }
}
